<?php
/**
 * User: LRZ
 * Date: 2020/1/21
 * Time: 13:34
 */

/**
 *  1160.拼写单词
 *
 *  标签：数组、哈希表
 *
 *  给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
 *  假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
 *  注意：每次拼写时，chars 中的每个字母都只能用一次。
 *  返回词汇表 words 中你掌握的所有单词的 长度之和。
 *
 *  示例 1：
 *      输入：words = ['cat','bt','hat','tree'], chars = 'atach'
 *      输出：6
 *      解释：可以形成字符串 'cat' 和 'hat'，所以答案是 3 + 3 = 6。
 *
 *  示例 2：
 *      输入：words = ['hello','world','leetcode'], chars = 'welldonehoneyr'
 *      输出：10
 *      解释： 可以形成字符串 'hello' 和 'world'，所以答案是 5 + 5 = 10。
 *   
 *  提示：
 *      1 <= words.length <= 1000
 *      1 <= words[i].length, chars.length <= 100
 *      所有字符串中都仅包含小写英文字母
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$words = [
    'qobxtxjzdngkrzamsxzdvbvkiwijokwdyndqllhqpaoxzwonriclsm',
    'fahtqqnuzhhhrcblquaosdfdcqoskxcsdnhtwvvvzsxkpjprytieieniafnltxmuzwkdnttofpibi',
    'xedhntgrqegfs',
    'wrssfvsbcehbahbvojnzgacbgveitirkjmmyiorwykynqddgydzgfvlvplfnyumgxturxraonpchd',
    'hpmdzhpgijirecxzkuyhptiytnuscu',
    'xljgysrjjukphjgzbpn',
    'gmwbirxt',
    'yhvpsvsnhfmbmcpihnqtodspbvexnpgcqrrughbakbufyjispkquvfppkaffypdpnvikjygdaarcigipfhuvzzzbgw',
    'gvvbgpjolobpbxcnhnzuqrsqgrkanwmnnkqynakkooailoafunopsrlijqhaqmszssxikftcfoqsw',
    'naktgxfyuvuoh',
    'muui',
    'ghzqskipqprrzeligdjyowypeerogxonvztsq',
    'onosezgutawtzteoagbftclsqpfsxtwetourxjxurdqevrir',
    'fcskqxwkzsldsjihahalnw',
    'lsstgzxjxabcbspjwelqmhtnurgfmdtpaihxnxad',
    'nwrwtwetgjwooevhxhkzlvsyghtkldioyjhkkniepktqs',
    'utohzbqvkqkq',
    'vdoqnhtidgicevprrrwlbtldtaxpsxdhxhgbwlkbeglkbhrujtafswjkozdmdpvwhsuskofmxxtprtpopacslinwozth',
    'zqlzxpemomnbzxlorvlkxt',
    'kubshvnldnkofitnnjere',
    'czxmqpowzzhdbhgtlqdokrzxowsvwyavfhcycctgdvrsfzmanrlktfaetnuayrqkvhcbxezfahkrxgaaztovrxuhnll',
    'rrcesnfbxglhjawldnnuiiepdsofbrsbjczlemusqwvenicxmtdmpwfrnizymfmqynvtkbrmablcugroshc',
    'thholqebekkysstqzlbbdapktxumygplqganucwnahmrihiraxdnvbiaqhykcti',
    'fagqnapzeeglbdzsbneosxmptmwopjcxztukhpjkqjmjbkpbzrfaqskctehyboeddmilkwlurcb',
    'wtjdykncubkduhxiwwusoxvzpnaxpnzdjmwddnonsmmvwmuaxghetgrwpoeqbprxgviwzagyqopfdakrqjgiy',
    'nsftehpgzstetbganbtozdopptseucdqkhzdmujnzjdvufqtikgeepttnrabb',
    'ozihktgnvljzhqwanxemtzxphzqvmoblvi',
    'iwdsrekqllbbyarzzmbqbvldvxctdeswiyahiwfoefhfsfwktdzaulnalewbusazjhcbtxjuck',
    'dylhds',
    'idnaddnzbodhjrpshhahnbbnrskruxszxeeyanumazvahktizectmmvjbhnhbrohsyqhrgq',
    'scyzsykrwzuozmbrbenfiqpxchtpmcxepjiglaeionsmbwrzeidupayusczcooudpcgkgspbuyzcdfymsejucb',
    'otpcfrhckxmnseayhwoyjjfkceaoznmmkikpdsuueyqmbsuelmhqnmdsjs',
    'xoghnhpypfiibqrpgtyux',
    'cxhpbcziptgandiwxtctdjpboiqwv',
    'gyjosuhwgbqpcdsdqadopdqozjxpzwxbqaffnxaddhgrxmunpidvpnijxnbawshcznkmprpgkhvzxmzbaftedgtfgjhaisdnva',
    'jlnxshfthqgzlnvjzztrnjswwsotpybxecyqhnfkbfwvmxpcs',
    'mtddspmqwbnoiajpexsuhxogarduzsoammqqelh',
    'sixkvxgnbalipwmkbcwpugpvolsvvlmaaeeobmoeogspbkbsskwjdqkite',
    'xhsutriuynfrldjbhexhxjgcfwcujvwsqfiaqwvjnkjkswdpaynelhryrzfeqjhajezmolk',
    'zfiredtxenzgtrkiamuoubetexzbnwkdtxbtihhtsfubnmryxq',
    'sot',
    'szgkkhuhkcnr',
    'firxkgvkzqlnallzwjispsizoawobemuhqrhpyvknasjzwctamfuonder',
    'vyei',
    'fidqszoicndwifns',
    'xkickycwzj',
    'gmybflbjunudxrwguzditaxmyadgdjeengut',
    'gvlwwnmrddhzwewugdtobauecealfhasyftgxkiqeluysxxmroukfziifpryvddggttojhcszeyjetbsldmorqnbuqreuxfw',
    'vbhuerxkcjlkamgruturkbrubbscmvzqruwvlrlyylcvuiothkhpznjzsfnyfoaqkziyjqzdreeygmtbdljwnaojexfgmjlup',
    'bxjvop',
    'aswdmctosieicucsjwxych',
    'lxbtlhnrfyaznrqgxrltmxkjmhdqjjgnvstxaygmuxznjfiiukm',
    'npncdabkmbgfhnedcmbfyjiplzwymgvsfrifvvjayobsygwolqbwkblqutakcshnlsqadtfiqmpauslvqd',
    'kuyemuuymacyvmahtagmcewkspverpjtjscccnrczchgkjzppdxcalxxcxrwnepk',
    'jxwouobfvzttz',
    'yucpsdhqvzboeezcqpxsepuuk',
    'iwbdmxdcbypnzqmgkrjhfivkrmnv',
    'lpqklgcwdvgbghfyoyejnpexrelywqfdtczflwetbxvzigtvisi',
    'dlasodatffcreungntdmezgfqklrabyymsnhdberufcrgpxgsziklznhdprbczhbxgtuslufycjronozdqumzlnidkvaydg',
    'oejzlmrrbdysqlezifcvgjnmvodfvmrnjmnfkejdbnnyljzjaxfecrfefdgarqbtwoijuktacywmsubtxtgzkbnstgrsrjpkdfe',
    'mlegvhxielwlfadlnqvnipcuizpdxgtvro',
    'vwgmwkbturocovaykdsjaftbtgmtwknnmhexfgcfchpwwgcgecfobbencotjizxbtdrijwfjxdsxanwfjyjamrxrdaiusgr',
    'xjmkcsekcorldyrjiavrhuhqtndujymc',
    'rmxwcaorznumwxgwnibnxwzvnxjhzwqzgmkgifnnnnzpgtsvprycjtdeirtpqbduursabbidzkfbexgthkoacagkb',
    'tkrsxhztwgvqxamjtexklnooaloydjhejlbasavskttwxiabarogvmfdfjttaxhgqljlbfnrvrwwbxkurhufiknoxfmemcv',
    'cojlyayladyrhofzetaddteqrjbyxtvyszgdorexqmgznqmuvemegbwki',
    'zktqnurtpttlcjgkmnprqeyeepqunfqqvjwuevwbvnaupyofwiqwhpyumyfwpjrruhleromrmpvczlkxqiuq',
    'gyxl',
    'qmhwlymfsjixvvjhkczylqcsnbjxliasetxciggtfl',
    'gizysqkqbyhzeagzsscvdigtcfiupyhqovaaioxfrphugxzrcjvwqwc',
    'hpgkulrmbaixnjiapmjiwhwsgromfqpxqkkiscjwpiicslwcijginxfiwqakeezeohhskxgvgdkezmqys',
    'vibswdyqaxjvqsffwmcismooheyhwzqvyzezluejztlgddshvwcryzcllaisxrygwqyyoiaivfvgtzicycyrkckv',
    'oyclwdejlifmocfjsbgmernsyitkfaahjxfnwnusrdypsziawlpsjgnavytdihpxcmugshnqbkyfts',
    'xwcbiporfbktpvqhznjuaxfcdykifuzwdsdhxirwwxinoffywgxscrtuwhvuwjejzqirsfijgguouapqpmfdnpsfm',
    'qffrjfkj',
    'rpynimubaxdgbrkdawgugnhobaowxdnzkiidworcsnejgqctftyksvbhiwkcnyffmsbxwptqn',
    'oeqdvldvfbklukstxwomapaauaozblhxudkdxihepqagndnlkvbqhluscvczhrsrhodnftoszhjdymuywdtjgzbmkrdf',
    'xviupppkeswkctwlqwyuhokbhqqjshmaeiouhununbhrkabacenkg',
    'habomjnlznqvckmowgelhnglfizogckplbymkdowfpicxydzgoskckraxpdysksvzezcpg',
    'zemawxwjeowraaqsqytsshtavnvoyiyollelxqabmjwhxtrdijiacbbjiiyzwkxboot',
    'jcnpsxnkbqdbh',
    'bftrbaurtzkftodotjguzjmwxrrmswxwclohotuanypmhtemmsaicwckowmcdmpnhcfzptekpgljfvwpqjgilxu',
    'bbaigjqxdmuchkkb',
    'effbptpwafzqbsebbjmvdcxdbmnlfqjklongafzkvaqmkehefedjxgxlbdhltihtgfqjjsdis',
    'lhuxgqpwcgpujfvvnlrxhgbiwxmxzhglyhkdkafafojtlkuxkmjwlxrd',
    'ussuyjqsxwsdhkjeipwycrkcxxjatoqhygzymgikqdnqiyyzlbcdlgtmneyickucbkpkza',
    'ykmsksjorovmdymlbgprvprnyxwppvwgmzfjsqouvgara',
    'wduqkbncayo',
    'qdfkyomjlhfozonwpdxllqdnvpohyijqmyymuclnydzmlqksntdfj',
    'ynzekkkljzrvnwclzcfgtvcmstxgadxpztofckypbgqgbnumnkeaqclaspzxjbygtkjznxeduhbksr',
    'aw',
    'jbremnahqoiqktpbkteefdkbrerrxmhqbbselpnfzapgmxidrhbixetaetjcroufa',
    'wtufuqgljvxzsurhviikdxyuythezjnvwrxqrykmotkhlphlyfljjsfugzwxxfqkc',
    'ytjuaagqnfxqwiopolnejmoxow',
    'oqoskpzkwxsffgeuuhdklidtmjobzayatyaqefgwgqbo',
    'qkhtpuhhkspffkpryvdjasbxhtfrmptpljszvtgvhfvqpxypxfdaphfqdmigzgfg',
    'goddugelwdvemxwureitzwqmbqeqtymrlrzahuxnpgufaagbpexwpoahvdnsyvgxw',
    'dfhxrctagxkuasofoejsalcerkbtsjwnbnoahsumzfyiiskhzzwyykeefszrzrbztbrzhxxgaajb',
    'tjsardsbhmhefysdqtbhzsxukbwdpioqaohloaancxdkkmofniojrvxj',
    'jzjozqfqiwyfadplibubtpcfxxfvjtbizxlmpaccjpihvnrtvfqtfiaztvfbednyemfmahbljdvykddawaujdksenm'
];
$chars = 'fcxpzkzkqeyeijquyfixvlzjpzomujrqzxeoynjiflnmdrpdkrm';
$res   = countCharacters($words, $chars);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function countCharacters($words, $chars)
{
    $res     = 0;
    $strLen  = strlen($chars);
    $strHash = [];
    for ($i = 0; $i < $strLen; $i++) {
        if (isset($strHash[$chars[$i]])) {
            $strHash[$chars[$i]]++;
        } else {
            $strHash[$chars[$i]] = 1;
        }
    }
    foreach ($words as $k => $v) {
        $vStrLen   = strlen($v);
        $tempCount = 0;
        $tempHash  = $strHash;
        for ($i = 0; $i < $vStrLen; $i++) {
            if (!isset($tempHash[$v[$i]])) {
                break;
            }
            $tempHash[$v[$i]]--;
            if ($tempHash[$v[$i]] < 0) {
                break;
            }
            $tempCount++;
        }
        if ($tempCount === $vStrLen) {
            $res += $vStrLen;
        }
    }
    return $res;
}